package com.mystudy.algorithm.sort;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @program: infoalgorithm
 * @description: 快速排序
 * @author: zhouzhilong
 * @create: 2019-07-31 14:15
 **/
public class QuickSort {
    /**
     * logger
     */
    private static final Logger LOGGER = LoggerFactory.getLogger(QuickSort.class);


    @Test
    public void test() {
        int[] arr = new int[]{4, 1, 9, 5, 1, 9, 5, 6, 6, 9, 2, 15, 21, 96, 34};
        int[] sort = sort(arr, 0, arr.length - 1);
        LOGGER.debug("sort = [{}]", sort);
    }


    private int[] sort(int[] arr, int start, int end) {
        int left = start;
        int right = end - 1;
        int standard = arr[end];
        while (left != end) {
            if (left == right) {
                if (arr[left] > standard) {
                    arr[end] = (arr[left] + arr[end]) - (arr[left] = arr[end]);
                    break;
                }
            }
            if (arr[left] > standard) {
                if (arr[right] < standard) {
                    arr[right] = (arr[left] + arr[right]) - (arr[left] = arr[right]);
                } else {
                    right--;
                    continue;
                }
            }
            left++;
        }

        if(left -start >1){
            sort(arr, start, left - 1);
        }

        if(left<end){
            sort(arr, left + 1, end);
        }
        return arr;
    }
}
